package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(minimumTotal([][]int{{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}}))
	fmt.Println(minimumTotal([][]int{{-10}}))
}

func min(arg1, arg2 int) int {
	if arg1 < arg2 {
		return arg1
	}
	return arg2
}

func minimumTotal(triangle [][]int) int {
	dpprev := make([]int, len(triangle[len(triangle)-1]))
	dpnext := make([]int, len(triangle[len(triangle)-1]))
	dpprev[0] = triangle[0][0]
	for i := 1; i < len(triangle[len(triangle)-1]); i++ {
		dpprev[i] = math.MaxInt
		dpnext[i] = math.MaxInt
	}
	minVal := dpprev[0]
	for i := 1; i < len(triangle); i++ {
		dpnext[0] = dpprev[0] + triangle[i][0]
		minVal = dpnext[0]
		for j := 1; j < len(triangle[i]); j++ {
			dpnext[j] = min(dpprev[j-1], dpprev[j]) + triangle[i][j]
			if dpnext[j] < minVal {
				minVal = dpnext[j]
			}
		}
		dpprev, dpnext = dpnext, dpprev
	}
	return minVal
}
